package LinkedList;

public class MyLinkedList {

    static class ListNode{
        private ListNode prev;//前驱结点
        private ListNode next;//后继结点
        private int val;
        public ListNode(int val){
            this.val = val;
        }
    }
    private ListNode head;//头结点
    private ListNode last;//尾巴结点

    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head==null){
            head =node;
        }else {
            node.next = head;
            head.prev =node;
            head = node;
        }
    }
    //尾插法
    public void addLast(int data){
          ListNode node = new ListNode(data);
          if(last==null){
              last = node;
              head =node;
          }else {
              last.next =node;
              node.prev =last;
              last = node;
          }
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index<0||index>size()){
            System.out.println("index不合法！！！");
            return ;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = head;
        //先让cur走到index位置处
        while(index!=0){
            cur =cur.next;
            index--;
        }
        //此时cur已经到达index位置开始进行插入
        node.next =cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;

    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while(cur!=null){
           if(cur.val==key){
               return true;
           }
            cur = cur.next;
        }
       return false;
    }
    //删除第一次出现关键字为key的节点
//    public void remove(int key){
//        if(head==null) {
//            System.out.println("链表已经为空");
//            return;
//        }
//        //头删
//         if(head.val==key){
//             if(head.next ==null) {
//                 head = head.next;
//                 return ;
//             }else {
//                 head = head.next;
//                 head.prev = null;
//                 return;
//             }
//         }
//         //尾删
//         if(last.val==key){
//             last = last.prev;
//             last.next =null;
//             return;
//         }
//         //中间删除
//        ListNode cur = head;
//         while(cur!=null){
//                 if(cur.val==key){
//                     cur.prev.next =cur.next;
//                     cur.next.prev = cur.prev;
//                     return;
//                 }else {
//                     cur = cur.next;
//                 }
//             }
//         if(cur==null){
//             System.out.println(key+"在链表中不存在无法删除！！！");
//             return;
//         }
//
//    }
//    //删除所有值为key的节点
//    public void removeAllKey(int key){
//        if(head==null) {
//            System.out.println("链表已经为空");
//            return;
//        }
//        //中间删除
//        ListNode cur = head;
//        while(cur!=null){
//            if(cur.val==key){
//                if(cur==head){
//                    if(head.next ==null) {
//                        head = head.next;
//                        return ;
//                    }else {
//                        head = head.next;
//                        head.prev = null;
//                    }
//                }
//                    cur.prev.next = cur.next;
//                    cur.next.prev = cur.prev;
//            }else {
//                cur = cur.next;
//            }
//        }
//        if(cur==null){
//            System.out.println(key+"在链表中不存在无法删除！！！");
//            return;
//        }
//
//    }

    public void remove(int key){
         ListNode cur = head;
         while(cur!=null){
             if(cur.val==key){
                 if(cur==head){
                     head=head.next;
                     if(head!=null&&head.next!=null) {
                         head.prev = null;
                     }
                 }else {
                     cur.prev.next = cur.next;
                     if (cur.next != null) {
                         cur.next.prev = cur.prev;
                     } else {
                         last = last.prev;
                     }
                 }
             }else {
                 cur = cur.next;
             }
             return;
         }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur = head;
        while(cur!=null){
            if(cur.val==key){
                if(cur==head){
                    head=head.next;
                    if(head!=null&&head.next!=null) {
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        last = last.prev;
                    }
                }
            }else {
                cur = cur.next;
            }
            cur =cur.next;
        }

    }
    //得到单链表的长度
    public int size(){
        ListNode cur = head;
        int cnt =0;
        while(cur!=null){
            ++cnt;
            cur = cur.next;
        }
        return cnt;
    }
    public void display(){
        ListNode cur = head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void clear(){
       ListNode cur =head;
       while(cur!=null){
           ListNode curNext = cur.next;
           cur.prev=null;
           cur.next=null;
           cur = curNext;
       }
       head =null;
       last = null;
    }

}
